package com.lw.leetcode.binary.a;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 *
 * binary
 * LCP 18. 早餐组合
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/4 15:12
 */
public class BreakfastNumber {

    public static void main(String[] args) {
        BreakfastNumber test = new BreakfastNumber();

        // [2,1,1] [8,9,5,1] 9     8
//        int[] a = {2,1,1};
//        int[] b = {8,9,5,1};
//        int x = 9;

        // [7,3,4,3,9,9,10,8,8,3] [7,10,6,7,5,2,8,4,5,8] 5      3
        int[] a = {7,3,4,3,9,9,10,8,8,3};
        int[] b = {7,10,6,7,5,2,8,4,5,8};
        int x = 5;

        int i = test.breakfastNumber(a, b, x);
        System.out.println(i);
    }

    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        Arrays.sort(drinks);
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : staple) {
            if (map.get(i) == null) {
                int t = x - i + 1;
                int count = 0;
                if (t > 1) {
                    count = find(drinks, t);
                }
               map.put(i, count);
            }
            sum = (sum + map.get(i)) % 1000000007;
        }
        return sum;
    }

    public int find (int[] arr , int t) {
        int end = arr.length - 1;
        if (arr[0] >= t) {
            return 0;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (arr[m] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st + 1;
    }

}
